L'algorithme vorace probabiliste suit le patron de conception des algorithmes
voraces étudié en cours à la différence prêt que cet algorithme utilise une
fonction de choix probabiliste. 

\paragraph{Fitness proportionate selection}
Cette fonction de choix fonctionne virtuellement comme une roulette, où chaque
choix possible possède une quartier du cercle proportionnel au critère de
choix, ici en l'occurrence, le revenu \tsc{per capita}.  Un nombre aléatoire
est ensuite tiré et la roulette fais autant de tours (non entiers) que
nécessaire. Un résultat est retourné. La figure \ref{fig:roulette} illustre la
disposition des stations.

\begin{figure}[H]
\begin{center}
  \includegraphics[width=.5\textwidth]{img/roulette}
  \caption{Exemple de disposition de roulette\label{fig:roulette}}
\end{center}
\end{figure}

De cette manière, nous sentons que même si les choix aux plus grands revenus
\tsl{per capita} ont plus de chance d'être tirés, tout les choix sont
virtuellement possibles.

La complexité d'une telle fonction est $O(n)$ car la fonction doit tout
d'abord parcourir les stations pour établir la somme des coûts :
\code[C++]{}{code/fitness.cc}

\paragraph{Conclusion}
La complexité théorique de notre implémentation est donc de 
$$\mbox{Temps, dans tous les cas : } \Theta(n) * \Theta(n) = \Theta(n^2)$$
Cette complexité doit cependant pouvoir se ramener assez aisément à $O(n)$ car
il est possible de créer un fonction de choix de complexité constante.

Enfin, il ne faut pas oublier que la principale caractéristique de cette
algorithme est de ne pas assurer une solution optimale.

$$\mbox{Espace, dans tous les cas : } \Theta(n)$$
